Digital signal processors are well known in the art. Digital signal processors process signals and typically include a Multiply and Accumulate (MAC) unit. This is because for many signal processing applications, the operations of multiplication and addition (or accumulation) are frequently used.
In the field of communications, a Viterbi algorithm is also well known in the art. The Viterbi algorithm is applied to known states and determines the probability of their interconnection. If a signal is encoded e.g. with a convolution code, upon its receipt, it can be decoded in accordance with the Viterbi algorithm. The received signal, in digital form or binary bits, can be decoded in accordance with a trellis. A trellis is a state transition diagram, in which all states of a process (the encoder) are shown over discrete time instants "K". The trellis is formed by drawing all transitions from every state at time K to its possible successor states, typically at time "K+1." A typical trellis is formed by a plurality of combinations of two stage "butterflies." This is also well known in the art to be true, e.g. in case of rate -1/2 convolutional codes. Thus, in decoding a signal that is encoded in accordance with the Viterbi algorithm, it is frequently desired to calculate the output of the "butterfly".
This involves the calculation of a first pair of binary signals C.sub.2n and C.sub.2n+1 (which are the outputs of a two stage butterfly), based upon a second pair of binary signals C.sub.n and C.sub.n+m/2 (which are the inputs to the two stage butterfly) with a transitional signal a connecting the input to the output. The Viterbi algorithm calculates the following: EQU C.sub.2n =minimum (C.sub.n +a, C.sub.n+m/2 -a) EQU C.sub.2n+1 =minimum (C.sub.n -a, C.sub.n+m/2 +a)
As can be seen from the foregoing, the calculations of the outputs of a two stage butterfly require addition, comparison, and selection. The add-compare-select, in the prior art, has been accomplished by either dedicated hardware or by a general purpose computer operating with appropriate software.
As for the former, because typically the decoding of Viterbi algorithm involves signal processing, a DSP or some other hardware circuit must be provided along with the dedicated hardware to decode the Viterbi two stage butterfly. As for the latter, it suffers from the disadvantage that many clock cycles are required to calculate the two stage butterfly.